[Coding009] DataStructure
(单)链表的基本操作及图形化解释（手绘）

Ben 2023/07/29

More coding records
Get the knowledge flowing and circulating! :)

标题：(单)链表的基本操作

Demo | 整体代码展示（可直接运行）


xxxxxxxxxx
296
1
// 单链表的相关操作 
2

3
#include"stdio.h"  
4
#include"malloc.h"
5

6
#include"stdlib.h"
7

8
// 下面定义的各个符号常量可以用来作为有些函数的返回状态码
9
#define TRUE 1
10
#define FALSE 0
11
#define OK 1
12
#define ERROR 0
13
#define INFEASIBLE -1
14

15
typedef int Status;  // 函数返回状态类型
16

17
typedef int ElemType;  // 链表元素类型
18

19
// 定义单链表结点类型
20
typedef struct LNode 
21
{
22
    ElemType data;
23
    struct LNode *next;  // 指向后继结点
24
}ListNode, *LinkList;
25

26
LinkList InitList()  // 初始化一带头结点的链表并返回头结点的指针
27
{
28
    LinkList L;
29
    
30
    L = (LinkList)malloc(sizeof(ListNode));  // 创建头结点
31
    L->next = NULL;
32
    
33
    return L;
34
}
35

36
int ListLength(LinkList L)  // 求链表L的表长
37
{
38
    int n = 0;
39
    
40
    LinkList p;
41
    p = L->next;
42
    
43
    while (p != NULL)
44
    {
45
        n++;
46
        p = p->next;
47
    }
48
    return n;
49
}
50

51
Status ListEmpty(LinkList L)  // 判断链表L是否为空,为空返回TRUE，否则返回FASLE
52
{
53
    if(L->next == NULL)
54
        return TRUE;
55
    else
56
        return FALSE;
57
}
58

59
void ListInsert(LinkList L, int i, ElemType e)  // 在链表L的第i个元素前插入一个值为e的元素
60
{
61
    LinkList p = L;
62
    LinkList s;
63
    
64
    int j = 0;
65
    
66
    // 寻找第i个节点
67
    while(p && j < i - 1)
68
    {
69
        p = p->next;
70
        j++;
71
    }
72
    
73
    if(!p || j > i - 1)  // i > len + 1 或 i < 1
74
    {
75
        printf("插入位置不合理\n");
76
        exit(0);
77
    }
78
    
79
    s = (LinkList)malloc(sizeof(ListNode));
80
    s->data = e;
81
    s->next = p->next;
82
    p->next = s;
83
}
84

85
ElemType GetElem(LinkList L, int i)  // 取链表L中的第i个元素
86
{
87
    ElemType e;
88
    
89
    LinkList p = L->next;  // p指向第一个元素
90
    
91
    int j = 1;
92
    while(p && j < i)
93
    {
94
        p = p->next;
95
        ++j;
96
    }
97
    
98
    if(!p || j > i)
99
        return ERROR;
100
        
101
    e = p->data;
102
    return e;
103
}
104

105
void ListTravers(LinkList L)  // 输出链表L的所有元素
106
{
107
    LinkList p = L->next;
108
    
109
    if(p == NULL)
110
        printf("表为空");
111
    else
112
    {
113
        while(p != NULL)
114
        {
115
            printf("%d ", p->data);
116
            p = p->next;
117
        }
118
    }
119
    printf("\n");
120
}
121

122
int LocateElem(LinkList L, ElemType e)  // 在链表L中定位值为e的元素位置
123
{
124
    LinkList p = L->next;
125
    
126
    int i = 1;
127
    
128
    while(p && p->data != e)
129
    {   
130
        p = p->next;
131
        i++;
132
    }
133
    
134
    if(p == NULL) 
135
        return ERROR;
136

137
    return i;
138
}
139

140
void ListDelete(LinkList L, int i)  // 删除链表L的第i个元素
141
{
142
    LinkList p = L;
143
    LinkList q;
144
    
145
    int j = 0;
146
    while(p->next && j < i - 1)  // 定位p指向要删除元素的前一个节点
147
    {
148
        p = p->next;
149
        j++;
150
    }
151
    
152
    if(p->next == NULL || j > i - 1) // 删除位置不合理
153
        return;
154
        
155
    q = p->next;
156
    p->next = q->next;
157
    free(q);
158
}
159

160
void ClearList(LinkList L)  // 重置链表L为空表
161
{
162
    LinkList p = L->next;
163
    LinkList q = p->next;
164
    
165
    L->next = NULL;
166
    
167
    while(q != NULL)
168
    {
169
        free(p);
170
        p = q;
171
        q = p->next;
172
    }
173
    free(p);
174
}
175

176
void DestroyList(LinkList L)  // 销毁链表L
177
{
178
    LinkList p = L;
179
    LinkList q = p->next;
180
    while(q != NULL)
181
    {
182
        free(p);
183
        p = q;
184
        q = p->next;
185
    }
186
    free(p);
187
}
188

189
void Insert(LinkList L, ElemType x)  // 在非递减的有序表L中插入值为x的元素，插入后仍然保持是有序性
190
{
191
    LinkList p = L->next;
192
    LinkList q = L;
193
    LinkList s;
194
    
195
    while(p && p->data < x)  // p指向要插入位置的后一个位置，q指向前一个元素
196
    {
197
        q = p;
198
        p = p->next;
199
    }
200
    
201
    if(p == NULL)  // 表示要插在最后
202
    {
203
        s = (LinkList)malloc(sizeof(ListNode));
204
        s->data = x;
205
        q->next = s;
206
        p = s;
207
        p->next = NULL;
208
    }
209
    else
210
    {
211
        s = (LinkList)malloc(sizeof(ListNode));
212
        s->data = x;
213
        q->next = s;
214
        s->next = p;
215
    }
216
}
217

218
int main()
219
{
220
    LinkList list1;
221
    LinkList list2;
222
    
223
    ElemType x;
224
    int i;
225

226
    // 定义过InitList函数和ListLength函数后可以执行如下两句测试
227
    list1 = InitList();
228
    printf("list1.length = %d.\n", ListLength(list1));  // list1.length = 0
229

230
    // 定义过ListEmpty函数后可以执行如下if语句测试
231
    if(ListEmpty(list1))  // list1为空表
232
        printf("\nlist1为空表\n");
233
    else
234
        printf("\nlist1为非空表\n");
235
    
236
    // 定义过ListInsert函数后可以执行如下三条测试
237
    printf("\n请按顺序输入10到100, 共10个整数创建链表：\n");
238
    for(i = 1; i <= 10; i++)  // 测试时依次输入10,20,30,40,50,60,70,80,90,100
239
    {
240
        scanf("%d", &x);
241
        ListInsert(list1, i, x);
242
    }
243
    printf("\nlist1.length = %d.\n", ListLength(list1));  // list1.length = 10
244

245
    // 定义过GetElem函数后可以执行如下一条句测试
246
    printf("\nlist1的第4个元素为%d.\n", GetElem(list1, 4));  // list1的第4个元素为40
247

248
    // 定义过ListTravers函数后可以执行如下两句测试
249
    printf("\n创建后list1表的内容为：\n");
250
    ListTravers(list1);  // 10 20 30 40 50 60 70 80 90 100
251
    
252
    // 定义过LocateElem函数后可以执行如下一条句测试
253
    printf("\n值为50的元素在list1表中的位序为%d.\n", LocateElem(list1, 50));  // 值为50的元素在list1表中的位序为5
254

255
    // 定义过ListDelete函数后可以执行如下三条句测试
256
    ListDelete(list1, 4);
257
    printf("\n删除第4个元素后：\n");
258
    ListTravers(list1);  // 10 20 30 50 60 70 80 90 100
259

260
    // 定义过ListInsert函数和ListTravers函数后可以执行如下三条句测试
261
    ListInsert(list1, 4, 44);
262
    printf("\n在第4个元素前插入44后：\n");
263
    ListTravers(list1);  // 10 20 30 44 50 60 70 80 90 100
264

265
    // 定义过ClearList函数后可以执行如下两条句测试
266
    ClearList(list1);
267
    printf("\nlist1.length = %d.\n", ListLength(list1));  // list1.length=0
268

269
    // 定义过DestroyList函数后可以执行如下语句测试      
270
    printf("list1.next = %d.\n", list1->next);  // list1.next = 0. 
271
    DestroyList(list1);
272
    printf("list1.next = %d.\n", list1->next);  // list1.next = 随机数.
273

274
    // 创建第二个非递减有序表
275
    list2 = InitList();  
276
    printf("\n请按顺序输入5个整数12,14,16,18,18创建非递减有序表：\n");
277
    for(i = 1; i <= 5; i++)  // 测试时依次输入12,14,16,18,18
278
    {
279
        scanf("%d", &x);
280
        ListInsert(list2, i, x);
281
    }
282

283
    // 定义过Insert函数后可以执行如下语句测试
284
    Insert(list2, 17);
285
    printf("\n插入17之后的list1表的内容为：\n");
286
    ListTravers(list2);  // 12,14,16,17,18,18
287
    
288
    return 0;
289
}
290

291
/*
292
测试样例：
293
 
294
10 20 30 40 50 60 70 80 90 100
295
12 14 16 17 18 18
296
*/

→ 分模块代码解释 - `头部`


xxxxxxxxxx
18
1
// 头部
2
// 链表的相关操作 
3

4
#include"stdio.h"  
5
#include"malloc.h"
6

7
#include"stdlib.h"
8

9
// 下面定义的各个符号常量可以用来作为有些函数的返回状态码
10
#define TRUE 1
11
#define FALSE 0
12
#define OK 1
13
#define ERROR 0
14
#define INFEASIBLE -1
15

16
typedef int Status;  // 函数返回状态类型
17

18
typedef int ElemType;  // 链表元素类型

还记得[Coding004]吗？typedef v.s #define

001

→ 分模块代码解释 - `单链表结点类型`


xxxxxxxxxx
6
1
// 定义单链表结点类型
2
typedef struct LNode 
3
{
4
    ElemType data;
5
    struct LNode *next;  // 指向后继结点
6
}ListNode, *LinkList;

学习的方法之一：类别。把不熟悉的类比到熟悉的知识上。（如果有错误，欢迎指正哦~ :P）

002

→ 分模块代码解释 - `单链表的初始化`


xxxxxxxxxx
9
1
LinkList InitList()  // 初始化一带头结点的链表并返回头结点的指针
2
{
3
    LinkList L;
4
    
5
    L = (LinkList)malloc(sizeof(ListNode));  // 创建头结点
6
    L->next = NULL;
7
    
8
    return L;
9
}

注意谁是指针（LinkList），谁不是指针（ListNode）.

003

→ 分模块代码解释 - `单链表求长度`


xxxxxxxxxx
14
1
int ListLength(LinkList L)  // 求链表L的表长
2
{
3
    int n = 0;
4
    
5
    LinkList p;
6
    p = L->next;
7
    
8
    while (p != NULL)
9
    {
10
        n++;
11
        p = p->next;
12
    }
13
    return n;
14
}

什么是空的链表？
就是不含有实际意义值的链表：只有一个dummy结点的链表，后面没有链上任何东西！

004

→ 分模块代码解释 - `单链表判空`


xxxxxxxxxx
7
1
Status ListEmpty(LinkList L)  // 判断链表L是否为空,为空返回TRUE，否则返回FASLE
2
{
3
    if(L->next == NULL)
4
        return TRUE;
5
    else
6
        return FALSE;
7
}

空链表！只有dummy伪结点的链表。

005

→ 分模块代码解释 - `单链表插入操作：在第i个元素前插入`


xxxxxxxxxx
25
1
void ListInsert(LinkList L, int i, ElemType e)  // 在链表L的第i个元素前插入一个值为e的元素
2
{
3
    LinkList p = L;
4
    LinkList s;
5
    
6
    int j = 0;
7
    
8
    // 寻找第i个节点
9
    while(p && j < i - 1)
10
    {
11
        p = p->next;
12
        j++;
13
    }
14
    
15
    if(!p || j > i - 1)  // i > len + 1 或 i < 1
16
    {
17
        printf("插入位置不合理\n");
18
        exit(0);
19
    }
20
    
21
    s = (LinkList)malloc(sizeof(ListNode));
22
    s->data = e;
23
    s->next = p->next;
24
    p->next = s;
25
}

在链表中插入/删除一个元素的重要前提：先找到待操作的元素的前一个位置，不然链表会断掉！

006

→ 分模块代码解释 - `单链表取第i个元素`


xxxxxxxxxx
19
1
ElemType GetElem(LinkList L, int i)  // 取链表L中的第i个元素
2
{
3
    ElemType e;
4
    
5
    LinkList p = L->next;  // p指向第一个元素
6
    
7
    int j = 1;
8
    while(p && j < i)
9
    {
10
        p = p->next;
11
        ++j;
12
    }
13
    
14
    if(!p || j > i)
15
        return ERROR;
16
        
17
    e = p->data;
18
    return e;
19
}

如果搞不清下标怎么操作的，就自己举个demo，画一画！

007

→ 分模块代码解释 - `单链表元素遍历`


xxxxxxxxxx
16
1
void ListTravers(LinkList L)  // 输出链表L的所有元素
2
{
3
    LinkList p = L->next;
4
    
5
    if(p == NULL)
6
        printf("表为空");
7
    else
8
    {
9
        while(p != NULL)
10
        {
11
            printf("%d ", p->data);
12
            p = p->next;
13
        }
14
    }
15
    printf("\n");
16
}

链表的经典移动操作：p = p->next;

008

→ 分模块代码解释 - `查找元素e的位置`


xxxxxxxxxx
17
1
int LocateElem(LinkList L, ElemType e)  // 在链表L中定位值为e的元素位置
2
{
3
    LinkList p = L->next;
4
    
5
    int i = 1;
6
    
7
    while(p && p->data != e)
8
    {   
9
        p = p->next;
10
        i++;
11
    }
12
    
13
    if(p == NULL) 
14
        return ERROR;
15

16
    return i;
17
}

切记：p是指针。可以理解为一个值，也可以理解为一个块。这里用橙色方框表示，是不是看起来更清晰了！

009

→ 分模块代码解释 - `单链表删除指定位置上的元素`


xxxxxxxxxx
19
1
void ListDelete(LinkList L, int i)  // 删除链表L的第i个元素
2
{
3
    LinkList p = L;
4
    LinkList q;
5
    
6
    int j = 0;
7
    while(p->next && j < i - 1)  // 定位p指向要删除元素的前一个节点
8
    {
9
        p = p->next;
10
        j++;
11
    }
12
    
13
    if(p->next == NULL || j > i - 1) // 删除位置不合理
14
        return;
15
        
16
    q = p->next;
17
    p->next = q->next;
18
    free(q);
19
}

在链表中插入/删除一个元素的重要前提：先找到待操作的元素的前一个位置，不然链表会断掉！

010

→ 分模块代码解释 - `单链表的清空`


xxxxxxxxxx
15
1
void ClearList(LinkList L)  // 重置链表L为空表
2
{
3
    LinkList p = L->next;
4
    LinkList q = p->next;
5
    
6
    L->next = NULL;
7
    
8
    while(q != NULL)
9
    {
10
        free(p);
11
        p = q;
12
        q = p->next;
13
    }
14
    free(p);
15
}

→ 分模块代码解释 - `单链表的销毁`


xxxxxxxxxx
12
1
void DestroyList(LinkList L)  // 销毁链表L
2
{
3
    LinkList p = L;
4
    LinkList q = p->next;
5
    while(q != NULL)
6
    {
7
        free(p);
8
        p = q;
9
        q = p->next;
10
    }
11
    free(p);
12
}

概念明晰：
清空：保留头部的dummy伪结点；
销毁：全部都free掉！

011

→ 分模块代码解释 - `一个关于元素插入的实例：在有序单链表中插入元素`


xxxxxxxxxx
28
1
void Insert(LinkList L, ElemType x)  // 在非递减的有序表L中插入值为x的元素，插入后仍然保持是有序性
2
{
3
    LinkList p = L->next;
4
    LinkList q = L;
5
    LinkList s;
6
    
7
    while(p && p->data < x)  // p指向要插入位置的后一个位置，q指向前一个元素
8
    {
9
        q = p;
10
        p = p->next;
11
    }
12
    
13
    if(p == NULL)  // 表示要插在最后
14
    {
15
        s = (LinkList)malloc(sizeof(ListNode));
16
        s->data = x;
17
        q->next = s;
18
        p = s;
19
        p->next = NULL;
20
    }
21
    else
22
    {
23
        s = (LinkList)malloc(sizeof(ListNode));
24
        s->data = x;
25
        q->next = s;
26
        s->next = p;
27
    }
28
}

重点操作：找到前一个元素！

012

重点强调

这里我整理学习的是C语言版的单链表实现。当然还有复杂的链表，比如双向链表。后面不一定会整理，但是这个单链表一定是重中之重！
重中之重的重中之重：在编程的过程要有意识地注意找到待操作元素的前一个元素的位置。
后面会遇到复杂的代码操作，可能会有很多指针，p, q, r, s...等等。要注意辨析每个指针的作用！

[Coding009] DataStructure (单)链表的基本操作及图形化解释（手绘）

标题：(单)链表的基本操作

Demo | 整体代码展示（可直接运行）

→ 分模块代码解释 - 头部

→ 分模块代码解释 - 单链表结点类型

→ 分模块代码解释 - 单链表的初始化

→ 分模块代码解释 - 单链表求长度

→ 分模块代码解释 - 单链表判空

→ 分模块代码解释 - 单链表插入操作：在第i个元素前插入

→ 分模块代码解释 - 单链表取第i个元素

→ 分模块代码解释 - 单链表元素遍历

→ 分模块代码解释 - 查找元素e的位置

→ 分模块代码解释 - 单链表删除指定位置上的元素

→ 分模块代码解释 - 单链表的清空

→ 分模块代码解释 - 单链表的销毁

→ 分模块代码解释 - 一个关于元素插入的实例：在有序单链表中插入元素

重点强调

[Coding009] DataStructure
(单)链表的基本操作及图形化解释（手绘）

→ 分模块代码解释 - `头部`

→ 分模块代码解释 - `单链表结点类型`

→ 分模块代码解释 - `单链表的初始化`

→ 分模块代码解释 - `单链表求长度`

→ 分模块代码解释 - `单链表判空`

→ 分模块代码解释 - `单链表插入操作：在第i个元素前插入`

→ 分模块代码解释 - `单链表取第i个元素`

→ 分模块代码解释 - `单链表元素遍历`

→ 分模块代码解释 - `查找元素e的位置`

→ 分模块代码解释 - `单链表删除指定位置上的元素`

→ 分模块代码解释 - `单链表的清空`

→ 分模块代码解释 - `单链表的销毁`

→ 分模块代码解释 - `一个关于元素插入的实例：在有序单链表中插入元素`